package Top200;

/**
 * @author zhangmin
 * @create 2022-02-25 11:55
 */
public class exist79 {
    boolean[][] visited;
    boolean backtrack(char[][] board,int i,int j,String word,int index){
        int m=board.length,n=board[0].length;
        if (index==word.length()){
            return true;
        }
        if (i<0||i>=m||j<0||j>=n||board[i][j]!=word.charAt(index)) return false;
        if (visited[i][j]) return false;
        visited[i][j]=true;
        boolean res=backtrack(board,i-1,j,word,index+1)||backtrack(board,i,j+1,word,index+1)||
                backtrack(board,i+1,j,word,index+1)||backtrack(board,i,j-1,word,index+1);
        visited[i][j]=false;
        return res;
    }
    public boolean exist(char[][] board, String word) {
        visited=new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (backtrack(board,i,j,word,0)){
                    return true;
                }
            }
        }
        return false;
    }
}
